#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//四数之和

vector<vector<int>> foursum(vector<int>& nums,int target){
    //先排序
    sort(nums.begin(),nums.end());

    vector<vector<int>> vv;

    int left, right;

    //i指针固定第一个值
    for(int i=0;i<nums.size();){
        //j指针用来固定第二个值
        for (int j = i + 1; j < nums.size();){
            long long targetj = (long long)target - nums[i] - nums[j];
            left = j + 1;
            right = nums.size() - 1;

            while(left<right){
                if(nums[left]+nums[right]>targetj){
                    right--;
                }
                else if(nums[left]+nums[right]<targetj){
                    left++;
                }
                else{
                    vv.push_back({nums[i], nums[j], nums[left++], nums[right--]});

                    //去重，同时处理边界情况
                    while(left<right&&nums[left]==nums[left-1]){
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }

            j++;
            while(j<nums.size()&&nums[j]==nums[j-1]){
                j++;
            }
        }

        i++;
        while(i<nums.size()&&nums[i]==nums[i-1]){
            i++;
        }
    }

    return vv;
}

int main(){
    vector<int> v = {1,-2,-5,-4,-3,3,3,5};
    int target = -11;

    vector<vector<int>> vv = foursum(v,target);

    for(auto v : vv){
        for(auto e : v){
            cout << e << " ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}